|
In mathematics, the graph partition problem is defined on data represented in the form of a graph ''G'' = (''V'',''E''), with ''V'' vertices and ''E'' edges, such that it is possible to partition ''G'' into smaller components with specific properties. For instance, a ''k''-way partition divides the vertex set into ''k'' smaller components. A good partition is defined as one in which the number of edges running between separated components is small. Uniform graph partition is a type of graph partitioning problem that consists of dividing a graph into components, such that the components are of about the same size and there are few connections between the components. Important applications of graph partitioning include scientific computing, partitioning various stages of a VLSI design circuit and task scheduling in multi-processor systems.〔 〕 Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see . == Problem complexity == Typically, graph partition problems fall under the category of NP-hard problems. Solutions to these problems are generally derived using heuristics and approximation algorithms.〔 〕 However, uniform graph partitioning or a balanced graph partition problem can be shown to be NP-complete to approximate within any finite factor.〔 Even for special graph classes such as trees and grids, no reasonable approximation algorithms exist,〔 〕 unless P=NP. Grids are a particularly interesting case since they model the graphs resulting from Finite Element Model (FEM) simulations. When not only the number of edges between the components is approximated, but also the sizes of the components, it can be shown that no reasonable fully polynomial algorithms exist for these graphs.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Graph partition」の詳細全文を読む スポンサード リンク
|